package com.jxb.three;

/**
 * 中位数
 *
 * @author jiaobo
 * @date Created in 2024/12/28 19:14
 **/
public class Medianof2SortedArrays_41 {

    public static void main(String[] args) {
        int[] num1 = {1,3};
        int[] num2 = {2,4};
        System.out.println(findMedianSortedArrays(num1, num2));
        // System.out.println((2+2+3)/2);
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //获取中间索引值
        int m = nums1.length, n = nums2.length;
        int left = (m+n+1)/2;
        int right = (m+n+2)/2;
        return (getkth(nums1,0,nums2,0,left)+getkth(nums1,0,nums2,0,right))/2.0;
    }

    public static double getkth(int[] nums1, int nums1Start, int[] nums2, int nums2Start, int k) {
        if (nums1Start > nums1.length - 1) {
            return nums2[nums2Start + k -1];
        }
        if (nums2Start > nums2.length - 1) {
            return nums1[nums1Start + k -1];
        }
        if (k == 1) {
            return Math.min(nums1[nums1Start],nums2[nums2Start]);
        }

        int num1Mid = Integer.MAX_VALUE,num2Mid = Integer.MAX_VALUE;
        if (nums1Start + k/2 - 1 < nums1.length) {
            num1Mid = nums1[nums1Start + k/2 - 1];
        }
        if (nums2Start + k/2 - 1 < nums2.length) {
            num2Mid = nums2[nums2Start + k/2 - 1];
        }

        //比较2值的大小
        if (num1Mid < num2Mid) {
            return getkth(nums1,nums1Start + k/2,nums2,nums2Start,k-k/2);
        }else {
            return getkth(nums1,nums1Start,nums2,nums2Start + k/2,k-k/2);
        }

    }

}
